﻿public class Solution {
    // 存储最终结果
    IList<IList<int>> result = new List<IList<int>>();
    List<int> res = new List<int>();
    public IList<IList<int>> Combine(int n, int k)
    {
        int start = 1;
        backtracking(start, n, k);
        return result;
    }

    private void backtracking(int start, int n, int k)
    {
        if (res.Count >= k)
        {
            result.Add(new List<int>(res));
            return;
        }

        for (int i = start; i <= n - (k-res.Count)+1; i++)
        {
            res.Add(i);
            backtracking(i+1, n, k);
            res.RemoveAt(res.Count-1); // 回溯
        }
    }

    public static void Main(string[] args)
    {
        int n = 4, k = 2;

        Solution solution = new Solution();
        IList<IList<int>> result = solution.Combine(n, k);
        
        // 打印结果
        foreach (IList<int> res in result)
        {
            foreach (int r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }
    
}